/***************************************************************************************************
 *Copyright(C),2010-2016,Sumscope
 *FileName	:  nzip.cpp
 *Author	:  scofined.qi
 *Version	:  1.0
 *Date		:  2017/09/15
 *Desc		:  //用于主要说明此程序文件完成的主要功能
 *Relation :
 *Others	:  //其他内容说明
 *Function :  //主要函数列表，每条记录应包含函数名及功能简要说明
 *History	:
 * //修改历史记录列表，每条修改记录应包含修改日期、修改者及修改内容简介
 ***************************************************************************************************/
#include "nzip.h"

#include <string.h>

#include <vector>
using namespace std;
// #define RUNTIME_TEST
#ifdef RUNTIME_TEST
#define RUN_TEST_CODE(CODE) \
  { CODE; }
#else
#define RUN_TEST_CODE(CODE)
#endif

/*
        压缩文件格式:
        1.文件布局
                开头是固定大小的结构体Head
                再次数Head.packcount个Package数组
                再次是变长的每个Package压缩区域
        2.Package压缩
                每个Package表示原始vector<int>的互不相交的一个整数范围段,要求最大-最小<65536
                使得同一个Package里的每个数字可以编码成ushort

                每个Package压缩后,有3个数据流base,gate,bits

                base数据流:每g_bestn个比特表示一个基数,基数个数是Package.basenum
                gate数据流:每1<<(16-g_bestn-g_gaten)个bit为一个子bit流,个数是Package.basenum
                bits数据流:具体多长由gate数据流的数据来决定


                每个Package里,根据g_bestn来划分成1<<g_bestn 个等长的部分
                每个部分管辖长度1<<(16-g_bestn)里的比特流,固定长度
                同时,此比特流中,每间隔1<<g_gaten个比特对应gate,如果全为0,那么

                压缩的关键:
*/

namespace {
static int g_bestn = 1;
static int g_gaten = 3;
}  // namespace
#ifdef WIN32
#include <windows.h>

#include <csignal>
#include <cstdarg>
void DbgError(char* smt, char* file, char* func, int line, const char* format,
              ...) {
#define ASSERTBUFSIZE 2048
  const size_t tsize = 1024;
  char buffer[tsize] = {0};
  char assertbuf[ASSERTBUFSIZE] = {0};

  memset(buffer, 0, tsize);
  memset(assertbuf, 0, ASSERTBUFSIZE * sizeof(char));

  va_list args;
  int ret;
  va_start(args, format);
  const char* pFileShort = strrchr(file, '\\');
  if (pFileShort == 0)
    pFileShort = file;
  else
    pFileShort++;

  ret = _snprintf_s(buffer, tsize, _TRUNCATE, "%s:%d:%s() ", pFileShort, line,
                    func);
  ret = vsprintf_s(assertbuf, ASSERTBUFSIZE, format, args);
  memmove_s(buffer + ret, tsize - ret, assertbuf, ret);

  va_end(args);

  UINT utype =
      MB_ABORTRETRYIGNORE | MB_ICONHAND | MB_SETFOREGROUND | MB_TASKMODAL;
  const char* title = "Microsoft Visual C++ Runtime Library";

  int nCode = MessageBoxA(NULL, assertbuf, title, utype);
  if (nCode == IDABORT) {
    raise(SIGABRT);
    _exit(3);
  }
  if (nCode == IDRETRY) {
    DebugBreak();
    return;
  }
  if (nCode == IDIGNORE) {
    return;
  }
  abort();
}
void DbgPrint(char* file, char* func, int line, const char* format, ...) {
  const size_t tsize = 2048;
  char buffer[tsize] = {0};
  memset(buffer, 0, tsize);
  va_list args;
  va_start(args, format);
  int ret = vsprintf_s(buffer, tsize, format, args);
  va_end(args);
  printf("\n%s", buffer);
}
#define DPRINT( \
    fmt,        \
    ...)  // DbgPrint(__FILE__, __FUNCTION__, __LINE__, fmt, __VA_ARGS__);
#define BASSERT(smt) \
  (void)((!!(smt)) || (DbgError(#smt, __FILE__, __FUNCTION__, __LINE__, ""), 0))

#else
#define DPRINT(fmt, ...)
#define BASSERT(smt)
#endif

class SequenceZip4Impl {
  typedef unsigned int uint;
  typedef unsigned short ushort;
  typedef unsigned char uchar;
#define ROUND_ALIGN(num, align) \
  ((num) % (align) == 0) ? (num) : (((num) / (align)) + 1) * (align)
  struct BitBlock {
    ushort base;          //
    vector<ushort> bits;  //
   public:
    BitBlock(ushort b, int fullBase, const std::vector<int>& numbers, int start,
             int end) {
      base = b;
      bits.reserve(end - start);
      for (int i = start; i < end; i++) {
        ushort num = numbers[i] - fullBase;
        bits.push_back(num);
      }
    }
  };
  struct Head {      // 压缩文件的第一个文件头
    int numcount;    // 整数个数
    int numstart;    // 第一个整数
    int numend;      // 末尾整数
    int packcount;   // 之后的Package数组的长度
    int totalbytes;  // 压缩完毕后的总大小,包括此文件头,之后的Package数组,之后的内容
    uint crc32;      // 之后内容的crc校验,包括Package数组
  };
  struct Package {  // 每个压缩处理单元的头部
    int offset;     // 偏移量
    int base;       // 基数
    int count;      // 整数个数
    int bestn;      // N 参数
    int gaten;      //
    int basenum;    // BitBlock的个数
    int basebytes;  // 头部字节
    int gatebytes;  //
    int bitsbytes;  // bits字节
  };
  struct PackageInfo {
    int istart, iend;
  };
  class CharBitmap {
    int m_bit_count;       // 比特位个数
    int m_bytes;           // 表示m_bits中前m_bytes个实际有效
    bool m_compressed;     // 是否压缩了
    vector<uchar> m_bits;  //
   public:
    CharBitmap() : m_bytes(0), m_bit_count(0), m_compressed(false) {}
    void Reset(int bitCount) {
      m_compressed = false;
      m_bit_count = bitCount;
      m_bytes = ROUND_ALIGN(bitCount, 8);
      m_bytes = m_bytes >> 3;
      m_bits.clear();
      m_bits.reserve(m_bytes);
      m_bits.assign(m_bytes, 0);
    }
    void Init(const uchar* mem, int bytes) {
      m_bytes = bytes;
      m_bit_count = bytes * 8;
      m_bits.clear();
      m_bits.assign(mem, mem + bytes);
    }
    int GetByteCount() const {
      BASSERT((int)m_bits.size() * 8 >= m_bit_count);
      BASSERT(m_bytes >= 0 && m_bytes <= (int)m_bits.size());
      return m_bytes;
    }
    inline uchar GetByte(int i) const { return m_bits[i]; }
    inline void SetBit(int index, bool set) {
      int slot = index >> 3;
      int pos = index - (slot << 3);
      if (set)
        m_bits[slot] |= 1 << pos;
      else
        m_bits[slot] &= ~(1 << pos);
    }
    int GetSetCount() const {
      int setCount = 0;
      for (int i = 0; i < m_bit_count; i++) {
        if (IsBitSet(i)) setCount++;
      }
      return setCount;
    }
    inline int GetBitCount() const { return m_bit_count; }
    inline bool IsBitSet(int index) const {
      int slot = index >> 3;
      int pos = index - (slot << 3);
      return (m_bits[slot] & (1 << pos)) != 0;
    }
    bool IsBitsClear(int index, int len) {
      int ni = index >> 3, nlen = len >> 3;
      if (index == ni << 3 && len == nlen << 3) {
        for (int i = 0; i < nlen; i++) {
          if (m_bits[i + ni] != 0) return false;
        }
        return true;
      }
      for (int i = 0; i < len; i++) {
        if (IsBitSet(index + i)) return false;
      }
      return true;
    }
    void Compress(int gate_size, CharBitmap& gate) {
      gate.Reset(m_bit_count / gate_size);
      for (int i = 0; i < GetBitCount(); i += gate_size) {
        gate.SetBit(i / gate_size, IsBitsClear(i, gate_size) ? false : true);
      }
      int set_count = GetSetCount();
      int lastpos = 0;
      for (int i = 0; i < gate.GetBitCount(); i++) {
        if (gate.IsBitSet(i)) {
          if (gate_size == 8) {
            m_bits[lastpos++] = m_bits[i];
          } else if (gate_size == 16) {
            m_bits[lastpos++] = m_bits[i * 2];
            m_bits[lastpos++] = m_bits[i * 2 + 1];
          } else if (gate_size == 32) {
            m_bits[lastpos++] = m_bits[i * 4];
            m_bits[lastpos++] = m_bits[i * 4 + 1];
            m_bits[lastpos++] = m_bits[i * 4 + 2];
            m_bits[lastpos++] = m_bits[i * 4 + 3];
          }
        }
      }
      // DPRINT("Compress Bits array %dbit ==> %dbit  ratio:%.2f", m_bit_count,
      // lastpos, m_bit_count*1.0 / lastpos);
      m_bytes = lastpos;
      m_bit_count = m_bytes << 3;
      for (int i = lastpos; i < (int)m_bits.size(); i++) m_bits[i] = 0;
      m_compressed = true;
    }
    void Uncompress(int gate_size, const CharBitmap& gate) {
      // BASSERT(gate.GetBitCount() == m_bits.size());
      int set_count = GetSetCount();
      int set_count2 = 0;
      int bit_count = gate.GetBitCount() * gate_size;
      int new_bytes = (ROUND_ALIGN(bit_count, 8)) >> 3;
      vector<uchar> bits;
      bits.reserve(new_bytes);
      bits.assign(new_bytes, 0);
      int lastpos = 0;
      for (int i = 0; i < gate.GetBitCount(); i++) {
        if (gate.IsBitSet(i))  // 一个bit可能代表2个char
        {
          if (gate_size == 8) {
            bits[i] = m_bits[lastpos++];
          } else if (gate_size == 16) {
            bits[i * 2] = m_bits[lastpos++];
            bits[i * 2 + 1] = m_bits[lastpos++];
          } else if (gate_size == 32) {
            bits[i * 4] = m_bits[lastpos++];
            bits[i * 4 + 1] = m_bits[lastpos++];
            bits[i * 4 + 2] = m_bits[lastpos++];
            bits[i * 4 + 3] = m_bits[lastpos++];
          }
        }
      }

      m_bit_count = bit_count;
      m_bytes = new_bytes;
      m_compressed = false;
      m_bits.clear();
      m_bits.reserve(bits.size());
      m_bits.assign(bits.begin(), bits.end());
      // m_bits.swap(bits);
      set_count2 = GetSetCount();
    }
  };
  class BitStreamEncoder {
    int m_unit_size;  // 一个单位占据的比特位数
    int m_bit_count;  // 已经加入的比特个数
    vector<uchar> m_bits;

   public:
    BitStreamEncoder(int unitSize, int predictCount)
        : m_unit_size(unitSize), m_bit_count(0) {
      m_bits.clear();
      m_bits.reserve(predictCount);
    }
    void AddShort(ushort num) {
      BASSERT(num >= 0 && num < (1 << m_unit_size));
      int bit_count = m_bit_count + m_unit_size;
      while (bit_count / 8 >= (int)m_bits.size()) {
        m_bits.push_back(0);
      }
      for (int i = 0; i < m_unit_size; i++)  // 低前高后
      {
        SetBit(m_bit_count + i, (num & (1 << i)) != 0);
      }
      m_bit_count += m_unit_size;
    }
    void AddBitmap(const CharBitmap& bmp) {
      int bit_count = bmp.GetBitCount();
      int bit_total = m_bit_count + bit_count;
      int bytes = (ROUND_ALIGN(bit_total, 8)) >> 3;
      m_bits.reserve(bytes);
      for (int i = 0; i < bit_count; i++) {
        SetBit(m_bit_count + i, bmp.IsBitSet(i));
      }
      m_bit_count += bit_count;
      // for (int i = 0; i < bmp.GetByteCount(); i++)
      //{
      //	m_bit_count += 8;
      //	m_bits.push_back(bmp.GetByte(i));
      // }
      // if (bmp.GetBitCount() < 8)
      //{

      //}
    }
    int Encode(char* buf, int len) {
      int size = ROUND_ALIGN(m_bit_count, 8);
      size = size >> 3;
      if (m_bits.size() > 0) {
        BASSERT(size <= len && size <= (int)m_bits.size());
        memcpy(buf, &m_bits[0], size);
      }
      return size;
    }
    void SetBit(int index, bool set) {
      int slot = index / 8;
      int pos = index - slot * 8;
      if (slot >= (int)m_bits.size()) m_bits.push_back(0);
      if (set)
        m_bits[slot] |= 1 << pos;
      else
        m_bits[slot] &= ~(1 << pos);
    }
  };
  class BitStreamDecoder {
    int m_unit_size;        // 一个单位占据的比特位数
    int m_bytes;            // 比特流的内存大小,字节数
    const uchar* m_memory;  // 比特流
   public:
    BitStreamDecoder(const uchar* mem, int bytes, int bitCount)
        : m_unit_size(bitCount), m_memory(mem), m_bytes(bytes) {}
    bool DecodeAsBool(int index) {
      // 将第index个单元解码成bool值,要求一个单位大小必须是1
      BASSERT(m_unit_size == 1);  // ushort是16个比特位
      BASSERT(index >= 0 && index * m_unit_size < m_bytes * 8);
      int bitindex = index * m_unit_size;
      int slot = bitindex >> 3;
      int pos = bitindex - (slot << 3);
      uchar uc = m_memory[slot];
      bool bset = (uc & (1 << pos)) != 0;
      return bset;
    }
    ushort DecodeAsShort(int index) {
      // 将第index个单元编码成ushort,要求一个单元大小必须不大于16
      BASSERT(m_unit_size <= 16);  // ushort是16个比特位
      BASSERT(index >= 0 && index * m_unit_size < m_bytes * 8);
      ushort code = 0;
      int bitStart = index * m_unit_size;  // 该单元在全局内存中的比特位置
      int bitEnd = bitStart + m_unit_size;

      int slot = bitStart >> 3;  // 该单元所在的位置,字节
      int bitPos = slot << 3;
      int pos = bitStart - (slot << 3);  // 该单元所在字节的比特位置
      int bitUsed = 0;                   // 已经消耗的比特位计数
      for (int i = slot; i < m_bytes && bitUsed < m_unit_size;
           i++, bitPos += 8) {
        ushort uc = m_memory[i];
        int posLow = (i == slot) ? pos : 0;
        int posHigh = (bitEnd - bitPos) >= 8 ? 8 : (bitEnd - bitPos);
        if (posHigh < 8) uc = uc & ((1 << posHigh) - 1);  // 去掉高位
        if (posLow > 0) uc = uc >> posLow;                // 去掉低位
        code = code | (uc << bitUsed);                    // 连接编码
        bitUsed += posHigh - posLow;
      }
      return code;
    }
    bool Decode(int index, int ncount, CharBitmap& bmp) {
      // 此种情况下一定是8比特对齐的,即m_unit_size % 8 == 0
      // 将第index个单位,到第index+ncout-1个单位的比特流解码成bmp
      BASSERT(index >= 0 && index * m_unit_size <= m_bytes * 8);
      BASSERT(ncount >= 1 && (index + ncount) * m_unit_size <= m_bytes * 8);
      BASSERT(
          m_unit_size % 8 ==
          0);  // 针对CharBitmap,要求必须是8的倍数,要求bestn必须在[1,10)区间内
      int nbyte = m_unit_size >> 3;
      bmp.Init(m_memory + index * nbyte, ncount * nbyte);
      return true;
    }
  };
  struct Block {   // 连续一整块
    ushort base;   // 基数
    ushort count;  // 基数之后的连续count个数字
  };
  class FullBlock {
    int m_capcity;  // m_bits中的比特个数,也是block_size
    int m_count;    // m_bits中有多少个1比特位
    int m_saved;
    int m_base_bit;  //
    ushort
        m_gate_unit;  // 只能是3或者4,表示m_bits中每2^m_gate_unit浓缩成m_gate的一个bit
                      // m_bitsz中每2^m_gate_unit个连续比特位都为0,对应的m_gate的一个bit才为0
                      // 否则为1
    ushort m_base;  // 基数
    CharBitmap m_gate;  // 每个bit为1表示m_bits中第x个m_gate_unit必定不为0
    CharBitmap m_bits;  // 每个bit为1,表示m_base+序号对应的整数存在
   public:
    FullBlock(int baseBitCount, ushort gateUnit) : m_gate_unit(gateUnit) {
      Reset(baseBitCount);
    }

    void Reset(int baseBitCount) {
      m_base_bit = baseBitCount;  //[1,13]
      m_base = 0;
      m_saved = 0;
      m_count = 0;
      m_capcity = 1 << (16 - baseBitCount);
      m_bits.Reset(m_capcity);
      m_gate.Reset(m_capcity >> m_gate_unit);
    }
    CharBitmap& GetGate() { return m_gate; }
    CharBitmap& GetBits() { return m_bits; }
    ushort GetBase() const { return m_base; }
    ushort GetGateUnit() const { return m_gate_unit; }
    int GetSaved() const { return m_saved; }
    void SetBase(ushort base) { m_base = base; }
    void SetBitBlock(int baseBitCount, const BitBlock& bblock) {
      Reset(baseBitCount);
      m_base = bblock.base;
      int gate_size = 1 << m_gate_unit;
      for (int i = 0; i < (int)bblock.bits.size(); i++) {
        m_bits.SetBit(bblock.bits[i], true);
      }
      m_bits.Compress(gate_size, m_gate);

      // Analysis(bblock);
    }
    void DecodeNumbers(int base, BitSet& bitmap) {
      m_bits.Uncompress(1 << m_gate_unit, m_gate);
      int ncount = m_bits.GetSetCount();
      int nbitcount = m_bits.GetBitCount();
      for (int i = 0; i < nbitcount; i++) {
        if (m_bits.IsBitSet(i))
          bitmap[base + i] = true;  // base+i已经减除了基数
      }
    }
    void DecodeNumbers(int base, std::vector<int>& numbers) {
      m_bits.Uncompress(1 << m_gate_unit, m_gate);
      int ncount = m_bits.GetSetCount();
      int nbitcount = m_bits.GetBitCount();
      for (int i = 0; i < nbitcount; i++) {
        if (m_bits.IsBitSet(i))
          numbers.push_back(base + i);  // base+i是最终整数,无基数
      }
    }
    int CalcTotalBitCount() {
      int bitcount = m_base_bit + m_gate.GetBitCount() + m_bits.GetBitCount();
      return bitcount;
    }
    void Analysis(const BitBlock& bblock) {
      // 实际测试表明,使用连续和离散的特征,无法进一步优化
      vector<Block> blocks;
      vector<ushort> scatters;
      ScanBlocks(bblock.bits, blocks, scatters, 4);
      int total =
          blocks.size() * sizeof(Block) + scatters.size() * sizeof(ushort);
      int nreal = CalcTotalBitCount();
      m_saved = total - nreal;
    }
    void ScanBlocks(const std::vector<ushort>& numbers,
                    std::vector<Block>& blocks, std::vector<ushort>& scatters,
                    ushort minBlock = 8) {
      ushort block_start = numbers[0];  // 连续开始值
      ushort block_last = numbers[0];   // 连续范围的上一个值
      for (int i = 1; i <= (int)numbers.size(); ++i) {
        ushort num = i < (int)numbers.size() ? numbers[i] : 0;
        if (i < (int)numbers.size() && num == block_last + 1) {
          block_last = num;
        } else {
          if (block_last + 1 - block_start >= minBlock) {
            Block bk;
            bk.base = block_start;
            bk.count = block_last + 1 - block_start;
            blocks.push_back(bk);
          } else {
            for (int k = block_start; k <= block_last; k++)
              scatters.push_back(k);
          }
          block_last = block_start = num;
        }
      }
    }
  };

 public:
  int Compress(const std::vector<int>& numbers, char* buf, int len) {
    // 计算有多少个包,
    vector<PackageInfo> packages;
    SplitPackages(numbers, packages);

    Head* phead = (Head*)buf;
    Package* packarray = (Package*)(phead + 1);

    // 开始对每个页面进行压缩编码
    char* ptr = (char*)&packarray[packages.size()];
    len -= (ptr - buf);
    int totalbytes = ptr - buf;
    int basebytes = 0, gatebytes = 0, bitsbytes = 0;
    for (int i = 0; i < (int)packages.size(); i++) {
      PackageInfo& info = packages[i];
      int bytes = CompressRange(numbers, info.istart, info.iend, ptr, len,
                                packarray[i]);
      packarray[i].offset = ptr - buf;
      ptr += bytes;
      len -= bytes;
      totalbytes += bytes;
      basebytes += packarray[i].basebytes;
      gatebytes += packarray[i].gatebytes;
      bitsbytes += packarray[i].bitsbytes;
    }

    DPRINT("[%6d - %6d]bestn:%2d base:%6d  gate:%6d  bits:%6d", 0,
           numbers.size(), g_bestn, basebytes, gatebytes, bitsbytes);
    DPRINT(" %6d  ==>   %6d  ratio:%.2f", numbers.size() * sizeof(int),
           totalbytes, numbers.size() * sizeof(int) * 1.0 / totalbytes);
    // 封装最后的头部数据,计算crc校验值
    phead->numcount = numbers.size();
    phead->numstart = numbers[0];
    phead->numend = numbers[numbers.size() - 1];
    phead->packcount = packages.size();
    phead->totalbytes = totalbytes;
    phead->crc32 = 0;
    // phead->crc32=calc_crc(packarray,totalbytes-sizeof(Head));
    return totalbytes;
  }
  bool GetPackInfo(const char* buf, int len, int& count, int& mi, int& mx) {
    if (buf == 0 || len <= sizeof(Head)) return false;
    const Head* phead = (const Head*)buf;
    if (phead->totalbytes != len) return false;
    count = phead->numcount;
    mi = phead->numstart;
    mx = phead->numend;
    return true;
  }
  int Uncompress(const char* buf, int len, BitSet& bitmap) {
    if (buf == 0 || len <= sizeof(Head)) return -1;
    const Head* phead = (const Head*)buf;
    if (phead->totalbytes != len) return -1;

    const Package* packarray = (const Package*)(phead + 1);
    bitmap.resize(phead->numend + 1 - phead->numstart);
    bitmap.clear();
    for (int i = 0; i < phead->packcount; i++) {
      const Package& pack = packarray[i];
      const uchar* packdata = (const uchar*)(buf + pack.offset);
      const uchar* bases = packdata;
      const uchar* gates = packdata + pack.basebytes;
      const uchar* bits = packdata + (pack.basebytes + pack.gatebytes);
      ExtractPackage(phead->numstart, pack, bases, gates, bits, bitmap);
    }
    return phead->numcount;
  }
  int Uncompress(const char* buf, int len, std::vector<int>& numbers) {
    if (buf == 0 || len <= sizeof(Head)) return -1;
    Head* phead = (Head*)buf;
    if (phead->totalbytes != len) return -1;

    Package* packarray = (Package*)(phead + 1);
    numbers.clear();
    numbers.reserve(phead->numcount);
    for (int i = 0; i < phead->packcount; i++) {
      Package& pack = packarray[i];
      const uchar* packdata = (const uchar*)(buf + pack.offset);
      const uchar* bases = packdata;
      const uchar* gates = packdata + pack.basebytes;
      const uchar* bits = packdata + (pack.basebytes + pack.gatebytes);
      ExtractPackage(pack, bases, gates, bits, numbers);
    }
    return numbers.size();
  }

 protected:
  void SplitPackages(const std::vector<int>& numbers,
                     std::vector<PackageInfo>& packages) {
    // 将整数序列按照65536切分成不同的页面,确保每个页面的末尾-开头<65536
    int base = numbers[0];
    int start = 0;
    for (int i = 1; i < (int)numbers.size(); i++) {
      int num = numbers[i];
      if (num - base >= 65536) {
        PackageInfo pi;
        pi.istart = start;
        pi.iend = i;
        packages.push_back(pi);
        base = num;
        start = i;
      }
    }
    PackageInfo pi;
    pi.istart = start;
    pi.iend = numbers.size();
    packages.push_back(pi);

    RUN_TEST_CODE(CheckPackages(numbers, packages););
  }
  void CheckPackages(const std::vector<int>& numbers,
                     const std::vector<PackageInfo>& packages) {
    for (int i = 0; i < (int)packages.size(); i++) {
      const PackageInfo& pi = packages[i];
      int first = numbers[pi.istart];
      int last = numbers[pi.iend - 1];
      BASSERT(pi.istart < pi.iend);
      BASSERT(first < last && last - first < 65536);
    }
  }
  void CheckBitBlocks(const std::vector<BitBlock>& bitmaps,
                      const std::vector<int>& numbers, int istart, int iend) {
    BASSERT(istart >= 0 && istart < iend && iend <= (int)numbers.size());
    vector<int> numbers1, numbers2;
    numbers1.reserve(iend - istart);
    numbers2.reserve(iend - istart);

    int pageBase = numbers[istart];
    for (int i = 0; i < (int)bitmaps.size(); i++) {
      const BitBlock& block = bitmaps[i];
      for (int k = 0; k < (int)block.bits.size(); k++)
        numbers1.push_back(pageBase + block.base + block.bits[k]);
    }
    for (int i = istart; i < iend; i++) numbers2.push_back(numbers[i]);

    BASSERT(numbers1.size() == numbers2.size());
    BASSERT(numbers1 == numbers2);
  }
  int CollectBitmaps(int targetn, const std::vector<int>& numbers, int istart,
                     int iend, std::vector<BitBlock>& bitmaps) {
    // 将整数序列numbers的单个页面再度按照固定间隔,划分成一个个BitBlock
    // 固定间隔尺寸:1 << (16 - targetn),也是一个BitBlock的能编码的整数个数
    // targetn:BitBlock的基数的编码的比特位长度
    BASSERT(targetn >= 0 && targetn <= 13);
    BASSERT(istart >= 0 && istart < iend && iend <= (int)numbers.size());
    int bytes = 0;
    int start = istart;
    int pageBase = numbers[istart];  // 页面基数
    int blockBase = 0;               // BitBlock基数
    int range = 1 << (16 - targetn);
    bitmaps.clear();
    bitmaps.reserve(65536 / range);
    for (int i = istart + 1; i < iend; i++) {
      int num = numbers[i] - pageBase;
      if (num - blockBase >= range) {
        bitmaps.push_back(
            BitBlock(blockBase, pageBase + blockBase, numbers, start, i));
        blockBase = (num / range) * range;
        start = i;
      }
    }
    bitmaps.push_back(
        BitBlock(blockBase, pageBase + blockBase, numbers, start, iend));
    RUN_TEST_CODE(CheckBitBlocks(bitmaps, numbers, istart, iend););
    return bitmaps.size();
  }
  void ExtractPackage(const Package& pack, const uchar* bases,
                      const uchar* gates, const uchar* bits,
                      std::vector<int>& numbers) {
    // 检查
    int block_size = 1 << (16 - pack.bestn);
    BitStreamDecoder base_stream(bases, pack.basebytes, pack.bestn);
    BitStreamDecoder gate_stream(gates, pack.gatebytes,
                                 block_size >> pack.gaten);
    BitStreamDecoder bits_stream(bits, pack.bitsbytes, 8);

    int ibit = 0;
    int ncount = numbers.size();
    FullBlock fb(pack.bestn, pack.gaten);
    ushort last = 0;
    for (int i = 0; i < pack.basenum; i++) {
      fb.Reset(pack.bestn);
      ushort base = base_stream.DecodeAsShort(i);
      // if (i > 0){ BASSERT(base == last + 1); }

      gate_stream.Decode(i, 1, fb.GetGate());
      int num = fb.GetGate().GetSetCount() * ((1 << pack.gaten) / 8);
      bits_stream.Decode(ibit, num, fb.GetBits());
      fb.DecodeNumbers(pack.base + base * block_size, numbers);
      ibit += num;
      last = base;
    }
    RUN_TEST_CODE(CheckAscend(numbers, ncount));
    BASSERT(ibit * sizeof(uchar) == pack.bitsbytes);
  }
  void ExtractPackage(int start, const Package& pack, const uchar* bases,
                      const uchar* gates, const uchar* bits, BitSet& bitmap) {
    // base 是原始压缩包中最小的整数,BitSet以此为基数
    // 检查
    int block_size = 1 << (16 - pack.bestn);
    BitStreamDecoder base_stream(bases, pack.basebytes, pack.bestn);
    BitStreamDecoder gate_stream(gates, pack.gatebytes,
                                 block_size >> pack.gaten);
    BitStreamDecoder bits_stream(bits, pack.bitsbytes, 8);

    int ibit = 0;
    FullBlock fb(pack.bestn, pack.gaten);
    ushort last = 0;
    for (int i = 0; i < pack.basenum; i++) {
      fb.Reset(pack.bestn);
      ushort base = base_stream.DecodeAsShort(i);
      // if (i > 0){ BASSERT(base == last + 1); }

      gate_stream.Decode(i, 1, fb.GetGate());
      int num = fb.GetGate().GetSetCount() * ((1 << pack.gaten) / 8);
      bits_stream.Decode(ibit, num, fb.GetBits());
      fb.DecodeNumbers(pack.base + base * block_size - start, bitmap);
      ibit += num;
      last = base;
    }
    BASSERT(ibit * sizeof(uchar) == pack.bitsbytes);
  }

  void CheckAscend(const std::vector<int>& numbers, int istart) {
    if ((int)numbers.size() <= istart) return;
    if (istart > 0) {
      BASSERT(numbers[istart - 1] < numbers[istart]);
    }
    for (int i = istart + 1; i < (int)numbers.size(); i++) {
      BASSERT(numbers[i - 1] < numbers[i]);
    }
  }
  void CheckCompressRange(const std::vector<int>& numbers, int istart, int iend,
                          const char* buf, int len, const Package& pack,
                          int bestn) {
    vector<int> extract_numbers, oldnums;
    extract_numbers.reserve(iend - istart);
    oldnums.reserve(iend - istart);
    for (int i = istart; i < iend; i++) {
      oldnums.push_back(numbers[i]);
    }
    const uchar* packdata = (const uchar*)(buf);
    const uchar* bases = packdata;
    const uchar* gates = packdata + pack.basebytes;
    const uchar* bits = packdata + (pack.basebytes + pack.gatebytes);
    ExtractPackage(pack, bases, gates, bits, extract_numbers);
    BASSERT(oldnums.size() == extract_numbers.size());
    if (oldnums.size() == extract_numbers.size()) {
      for (int i = 0; i < (int)oldnums.size(); i++) {
        int old = oldnums[i];
        int nnew = extract_numbers[i];
        BASSERT(old == nnew);
      }
    }
  }
  int CompressRange(const std::vector<int>& numbers, int istart, int iend,
                    char* buf, int len, Package& pack) {
    BASSERT((int)numbers.size() > 0 && istart >= 0 && istart < iend &&
            iend <= (int)numbers.size());
    BASSERT(buf != 0 && len > 0);

    // 可以依靠算法来计算最佳best_n,暂定为6
    int best_n = g_bestn;
    ushort gaten = g_gaten;
    int min_bytes = 0;
    int block_size = 1 << (16 - best_n);
    int bits_bytes = block_size >> 3;

    vector<BitBlock> bitmaps;
    CollectBitmaps(best_n, numbers, istart, iend, bitmaps);

    BitStreamEncoder base_encoder(best_n, bitmaps.size());
    BitStreamEncoder gate_encoder(block_size >> gaten, bitmaps.size());
    BitStreamEncoder bits_encoder(8, bitmaps.size() * bits_bytes);

    FullBlock fb(best_n, gaten);
    for (int i = 0; i < (int)bitmaps.size(); i++) {
      fb.SetBitBlock(best_n, bitmaps[i]);
      ushort base = fb.GetBase();
      BASSERT(base % block_size == 0);
      base_encoder.AddShort(base / block_size);
      gate_encoder.AddBitmap(fb.GetGate());
      bits_encoder.AddBitmap(fb.GetBits());
    }

    char* ptr = buf;
    int capcity = len;
    pack.offset = 0;
    pack.base = numbers[istart];
    pack.count = iend - istart;
    pack.bestn = best_n;
    pack.gaten = gaten;
    pack.basenum = bitmaps.size();
    pack.basebytes = base_encoder.Encode(ptr, capcity);
    ptr += pack.basebytes;
    capcity -= pack.basebytes;
    pack.gatebytes = gate_encoder.Encode(ptr, capcity);
    ptr += pack.gatebytes;
    capcity -= pack.gatebytes;
    pack.bitsbytes = bits_encoder.Encode(ptr, capcity);
    ptr += pack.bitsbytes;
    capcity -= pack.bitsbytes;
    DPRINT("[%6d - %6d]bestn:%2d base:%6d  gate:%6d  bits:%6d", istart, iend,
           best_n, pack.basebytes, pack.gatebytes, pack.bitsbytes);
    int size = ptr - buf;
    RUN_TEST_CODE(
        CheckCompressRange(numbers, istart, iend, buf, size, pack, best_n));
    return size;
  }

 public:
  int ConvertNumbersToBits(const std::vector<int>& numbers, uchar* bits,
                           int size) {
    // numbers的最大整数 必须<size*8
    if (numbers.size() <= 0) return 0;
    memset(bits, 0, size);
    int imax = numbers[0];
    int bmax = size << 3;
    int ncount = numbers.size();
    for (int i = 0; i < ncount; i++) {
      int index = numbers[i];
      int slot = index >> 3;
      int pos = index - (slot << 3);
      imax = imax < index ? index : imax;
      if (imax >= bmax) return -1;
      bits[slot] |= 1 << pos;
    }
    return imax;
  }
};
void SequenceZip4::SetBestN(int n) { g_bestn = n; }
void SequenceZip4::SetGateN(int n) { g_gaten = n; }
int SequenceZip4::Compress(const int* uniqAscendNumbers, int ncount, char* buf,
                           int size) {
  SequenceZip4Impl impl;
  vector<int> numbers;
  numbers.reserve(ncount);
  numbers.assign(uniqAscendNumbers, uniqAscendNumbers + ncount);
  return impl.Compress(numbers, buf, size);
}
int SequenceZip4::Uncompress(const char* buf, int size,
                             std::vector<int>& numbers) {
  if (buf == 0 || size <= 0) return -1;
  SequenceZip4Impl impl;
  int ncount = 0, nmin = -1, nmax = -1;
  if (impl.GetPackInfo(buf, size, ncount, nmin, nmax) && ncount > 0 &&
      nmax >= nmin) {
    if (impl.Uncompress(buf, size, numbers) > 0) {
      return ncount;
    }
  }
  return -1;
}
int SequenceZip4::Uncompress(const char* buf, int size, int* uniqAscendNumbers,
                             int capcity) {
  if (buf == 0 || size <= 0 || uniqAscendNumbers == 0 || capcity <= 0)
    return -1;
  SequenceZip4Impl impl;
  int ncount = 0, nmin = -1, nmax = -1;
  if (impl.GetPackInfo(buf, size, ncount, nmin, nmax) && ncount > 0 &&
      nmax >= nmin && ncount < capcity) {
    vector<int> numbers;
    if (impl.Uncompress(buf, size, numbers) > 0) {
      if ((int)numbers.size() > capcity) return -1;

      memcpy(uniqAscendNumbers, &numbers[0], numbers.size() * sizeof(int));
      return numbers.size();
    }
  }
  return -1;
}

bool SequenceZip4::GetPackInfo(const char* buf, int size, int& count, int& mi,
                               int& mx) {
  // 功能:检测压缩包是否正确,并获取整数个数,最小值,最大值
  SequenceZip4Impl impl;
  return impl.GetPackInfo(buf, size, count, mi, mx);
}
int SequenceZip4::UncompressAsBits(const char* buf, int len,
                                   unsigned char* bits, int size) {
  /*
          功能:将压缩后的数据包解压成比特位
          buf:压缩包
          len:压缩包的大小
          bits:比特位缓冲区
          size:比特位缓冲区的字节大小,要求整数中最大值<size*8
                   最大值可以通过GetPackInfo接口来获取
          返回值:
                   成功表示最大的整数
                   -1,表示解压失败
  */
  if (buf == 0 || len <= 0 || bits == 0 || size <= 0) return -1;
  SequenceZip4Impl impl;
  int ncount = 0, nmin = -1, nmax = -1;
  if (impl.GetPackInfo(buf, len, ncount, nmin, nmax) && ncount > 0 &&
      nmax >= nmin && nmax < size * 8) {
    vector<int> numbers;
    if (impl.Uncompress(buf, size, numbers) > 0) {
      return impl.ConvertNumbersToBits(numbers, bits, size);
    }
  }
  return -1;
}
int SequenceZip4::UncompressAsBits(const char* buf, int len, BitSet& bits) {
  /*
  功能:将压缩后的数据包解压成比特位
  buf:压缩包
  len:压缩包的大小
  bits:比特位缓冲区
  size:比特位缓冲区的字节大小,要求整数中最大值<size*8
  最大值可以通过GetPackInfo接口来获取
  返回值:
  成功表示最大的整数
  -1,表示解压失败
  */
  if (buf == 0 || len <= 0) return -1;
  SequenceZip4Impl impl;

  int ncount = 0, nmin = -1, nmax = -1;
  if (impl.GetPackInfo(buf, len, ncount, nmin, nmax) && ncount > 0 &&
      nmax >= nmin) {
    return impl.Uncompress(buf, len, bits);
  }
  return -1;
}
